package q2092_findAllPeople;

import java.util.*;

public class Solution_1 {
    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        int m = meetings.length;
        // 1.按时间排序
        Arrays.sort(meetings, Comparator.comparingInt(x -> x[2]));

        // 2.已知秘密的人设置为true
        boolean[] secret = new boolean[n];
        secret[0] = secret[firstPerson] = true;

        Map<Integer, List<Integer>> edges = new HashMap<>();//关联点

        for (int i = 0; i < m; ) {
            // 找到这轮的范围
            int j = i;
            while (j + 1 < m && meetings[j + 1][2] == meetings[i][2]) {
                ++j;
            }

            edges.clear();
            for (int k = i; k <= j; ++k) {
                int x = meetings[k][0];
                int y = meetings[k][1];
                // 加入关联点
                List<Integer> l = edges.getOrDefault(x, new ArrayList<>());
                l.add(y);
                edges.put(x, l);
                l = edges.getOrDefault(y, new ArrayList<>());
                l.add(x);
                edges.put(y, l);
            }

            // 当前范围已知点
            Queue<Integer> queue = new LinkedList<>();
            for (int u : edges.keySet()) {
                if (secret[u]) {
                    queue.offer(u);
                }
            }

            // 假设一个知道，则此轮关联点也必然知道
            while (!queue.isEmpty()) {
                int u = queue.poll();
                List<Integer> list = edges.getOrDefault(u, new ArrayList<>());
                for (int v : list) {
                    if (!secret[v]) {
                        secret[v] = true;
                        queue.offer(v);
                    }
                }
            }

            i = j + 1;
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (secret[i]) {
                ans.add(i);
            }
        }
        return ans;
    }
}
